package alo.p3.work;

import alo.p3.ListNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class deleteNode {

    //删除某节点，但是只能访问这一个结点
    deleteNode(ListNode node){
        node.setData(node.getNext().getData());
        node.setNext(node.getNext().getNext());
    }


    //删除链表中所有的值=val的结点
    //难点是要删除的结点为head
    class Solution {
        public ListNode removeElements(ListNode head, int val) {
            //新建一个pre前驱
            ListNode s=new ListNode(0);
            s.setNext(head);
            ListNode pre=s;
            ListNode c1=head;
            while(c1!=null){
                if(c1.getData()==val){
                    pre.setNext(c1.getNext());
                }else {
                    pre=c1;
                }
                c1=c1.getNext();
            }
            return s.getNext();
        }
    }

    /*给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。*/

    //这种方法也可以删除非排序的链表
    class Solution1 {
        public ListNode deleteDuplicates(ListNode head) {
            ListNode c1=head;
            HashMap<Integer,Boolean> map=new HashMap<>();
            ArrayList<Integer> arrayList=new ArrayList();
            while (c1!=null){
                if (!map.containsKey(c1.getData()))
                    map.put(c1.getData(),false);
                else arrayList.add(c1.getData());
                c1=c1.getNext();
            }
            for (int i = 0; i < arrayList.size(); i++) {
                head=removeElements(head,arrayList.get(i));
            }
            return head;
        }
        public ListNode removeElements(ListNode head, int val) {
            //新建一个pre前驱
            ListNode s=new ListNode(0);
            s.setNext(head);
            ListNode pre=s;
            ListNode c1=head;
            while(c1!=null){
                if(c1.getData()==val){
                    pre.setNext(c1.getNext());
                }else {
                    pre=c1;
                }
                c1=c1.getNext();
            }
            return s.getNext();
        }
    }
    //双指针法
    class Solution2 {
        public ListNode deleteDuplicates(ListNode head) {
            if(head==null || head.getNext()==null) {
                return head;
            }
            ListNode dummy = new ListNode(-1);
            dummy.setNext(head);
            ListNode a = dummy;
            ListNode b = head;
            while(b!=null && b.getNext()!=null) {
                //初始化的时a指向的是哑结点，所以比较逻辑应该是a的下一个节点和b的下一个节点
                if(a.getNext().getData()!=b.getNext().getData()) {
                    a = a.getNext();
                    b = b.getNext();
                }
                else {
                    //如果a、b指向的节点值相等，就不断移动b，直到a、b指向的值不相等 
                    while(b!=null && b.getNext()!=null && a.getNext().getData()==b.getNext().getData()) {
                        b = b.getNext();
                    }
                    a.setNext(b.getNext());
                    b = b.getNext();
                }
            }
            return dummy.getNext();
        }
    }
    
    //使用递归的方法
    class Solution3{
        public ListNode deleteDuplicates(ListNode head) {
            if (head == null || head.getNext() == null) {
                return head;
            }
            //如果相等，移动到重复的最后一个结点，在递归最后一个节点的next
            if (head.getData() == head.getNext().getData()) {
                while (head != null && head.getNext() != null && head.getData() == head.getNext().getData()) {
                    head = head.getNext();
                }
                return deleteDuplicates(head.getNext());
            } else {
                head.setNext(deleteDuplicates(head.getNext()));
                return head;
            }
        }

    }
    /*给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

    示例 1:

    输入: 1->1->2
    输出: 1->2
    */
    //上一个删除的变形
    class Solution3x{
        public ListNode deleteDuplicates(ListNode head) {
            if (head == null || head.getNext() == null) {
                return head;
            }
            //如果相等，移动到重复的最后一个结点，在递归最后一个节点的next
            if (head.getData() == head.getNext().getData()) {
                while (head != null && head.getNext() != null && head.getData() == head.getNext().getData()) {
                    head = head.getNext();
                }
                return deleteDuplicates(head);
            } else {
                head.setNext(deleteDuplicates(head.getNext()));
                return head;
            }
        }

    }

    /*
    *
    * 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

    示例1:

     输入：[1, 2, 3, 3, 2, 1]
     输出：[1, 2, 3]
     * */
    //哈希set
    class Solution4 {
        public ListNode removeDuplicateNodes(ListNode head) {
            if(head==null) return head;
            HashSet<Integer> set=new HashSet<Integer>();
            set.add(head.getData());
            ListNode c1=head.getNext(),c2=head;
            while(c1!=null){
                if(!set.contains(c1.getData())){
                    set.add(c1.getData());
                    c2.setNext(c1);
                    c2=c2.getNext();
                }
                c1=c1.getNext();
            }
            c2.setNext(null);
            return head;
        }
    }
    //双指针法（暴力法）
    class Solution5 {
        public ListNode removeDuplicateNodes(ListNode head) {
            ListNode ob = head;
            while (ob != null) {
                ListNode oc = ob;
                while (oc.getNext() != null) {
                    if (oc.getNext().getData() == ob.getData()) {
                        oc.setNext(oc.getNext().getNext());
                    } else {
                        oc = oc.getNext();
                    }
                }
                ob = ob.getNext();
            }
            return head;
        }
    }

    //使用int数组进行数值比较
    public ListNode removeDuplicateNodes(ListNode head) {
        int[] bits = new int[20000 / 32 + 1];
        ListNode cur = head;
        while (cur != null && cur.getNext() != null) {
            bits[cur.getData() / 32] |= 1 << (cur.getData() % 32);
            if ((bits[cur.getNext().getData() / 32] & (1 << (cur.getNext().getData() % 32))) != 0)
                cur.setNext(cur.getNext().getNext());
            else
                cur = cur.getNext();
        }
        return head;
    }


}
